#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int n;
int l[N], r[N];
// 先序遍历：根左右
void dfs1(int p)
{
    if(p == 0) return;
    cout << p << " ";
    dfs1(l[p]);
    dfs1(r[p]);
}
// 中序遍历：左根右
void dfs2(int p)
{
    if(p == 0) return;
    dfs2(l[p]);
    cout << p << " ";
    dfs2(r[p]);
}
// 后序遍历：左右根
void dfs3(int p)
{
    if(p == 0) return;
    dfs3(l[p]);
    dfs3(r[p]);
    cout << p << " ";
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
    }
    dfs1(1);
    cout << endl;
    dfs2(1);
    cout << endl;
    dfs3(1);
    cout << endl;
    return 0;
}